package _02_链表;

public class _206_反转链表 {

    // 返回的话始终是最后一个节点，并且递归也算一种遍历，只不过是从后往前遍历
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        // 遍历的过程
        head.next.next = head;
        head.next = null;
        return newHead;
    }


    // 非递归
    public ListNode reverseList1(ListNode head) {
        // 存在空的情况
        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

    // 递归
    public ListNode reverseList2(ListNode head) {
        // 递归出口
        if (head == null || head.next == null) return head;
        // 2层判断
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

}
